home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / UGRAPH.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  2.9 KB  |  78 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.2 Undirected graphs (ugraph)}
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $G$ of the data type $ugraph$ consists of a set of nodes $V$ and a 
  8. set of undirected edges $E$. Every edge $e \in E$ is a set of two nodes 
  9. $\{v,w\}$, $v$ and $w$ are called the endpoints of $e$. With every node $v$ is 
  10. associated the list of its adjacent edges 
  11. $adj\_list(v) = \{\ e \in E\ | v \in e\ \}$.
  12.  
  13. \def\name{$ugraph$}
  14. \def\type{ugraph}
  15.  
  16. \bigskip
  17. {\bf 2. Creation}
  18.  
  19. \create G {}
  20.  
  21. creates an instance $G$ of type $ugraph$ and initializes it to the
  22. empty undirected graph.
  23.  
  24.  
  25. \bigskip
  26. {\bf 3. Operations }
  27. \medskip
  28. Most operations are the same as for directed graphs. The following operations
  29. are either additional or have different effects.
  30. \medskip
  31. \+\cleartabs & \hskip 1.5truecm & \hskip 5.8truecm &\cr
  32. \+\op node opposite {node\ v,\ edge\ e} 
  33.                                {returns $w$ if $e = \{v,w\}$, nil otherwise}
  34. \smallskip
  35. \+\op int  degree {node\ v} 
  36.                                {returns the degree of node $v$.}
  37. \smallskip
  38. \+\op edge new\_edge {node\ v,\ node\ w}
  39.                              {inserts the undirected edge $\{v,w\}$ into $G$ by}
  40. \+\nop                       {appending it to the adjacency lists of both}
  41. \+\nop                       {$v$ and $w$ and returns it }
  42. \smallskip
  43. \+\op edge new\_edge {node\ v,\ node\ w,\ edge\ e1,\ edge\ e2,\ dir1=after,\ dir2=after} {}
  44. \+\nop                {inserts the undirected edge $\{v,w\}$ after (if $dir1$}
  45. \+\nop                {$=after$) or before (if $dir1=before$) the edge}
  46. \+\nop                {$e1$ into the adjacency list of $v$ and after (if $dir2$}
  47. \+\nop                {$=after$) or before (if $dir2=before$) the edge }
  48. \+\nop                {$e2$ into the adjacency list of $w$ and returns it}
  49. \smallskip
  50. \+\op edge adj\_succ {edge\ e,\ node\ v} 
  51.                              {returns the successor of edge $e$ in the}
  52. \+\nop                       {adjacency list of $v$. }
  53. \smallskip
  54. \+\op edge adj\_pred {edge\ e,\ node\ v} 
  55.                              {returns the predecessor of edge $e$ in the}
  56. \+\nop                       {adjacency list of $v$. }
  57. \smallskip
  58. \+\op edge cyclic\_adj\_succ {edge\ e,\ node\ v} {}
  59. \+\nop                       {returns the cyclic successor of edge $e$ in the}
  60. \+\nop                       {adjacency list of $v$. }
  61. \smallskip
  62. \+\op edge cyclic\_adj\_pred {edge\ e,\ node\ v} {}
  63. \+\nop                       {returns the cyclic predecessor of edge $e$ in the}
  64. \+\nop                       {adjacency list of $v$. }
  65.  
  66.  
  67. \bigskip
  68. {\bf 4. Implementation}
  69.  
  70. Undirected graphs are implemented like directed graphs by adjacency lists. 
  71. The adjacency list of a node $v$ contains all edges $\{v,w\}$ of the graph.
  72. Most operations take constant time, except of all\_nodes, all\_edges, 
  73. del\_all\_nodes, del\_all\_edges, clear, write, and read which take time 
  74. $O(n+m)$, where $n$ is the current number of nodes and $m$ is the current 
  75. number of edges. The space requirement is $O(n+m)$.
  76.  
  77. \vfill\eject
  78.